<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.3/css/all.min.css">
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.css">
  <script src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.js"></script>

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"ackermannn.github.io","root":"/","images":"/images","scheme":"Gemini","version":"8.3.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>
<meta property="og:type" content="website">
<meta property="og:title" content="Ackermannn&#39;s Blog">
<meta property="og:url" content="http://ackermannn.github.io/index.html">
<meta property="og:site_name" content="Ackermannn&#39;s Blog">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="Ackermannn">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://ackermannn.github.io/">


<script data-pjax class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : true,
    isPost : false,
    lang   : 'zh-CN'
  };
</script>
<title>Ackermannn's Blog</title>
  




  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Ackermannn's Blog</h1>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
        <li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li>
        <li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
        <li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-overview-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Ackermannn"
      src="/images/dl.jpg">
  <p class="site-author-name" itemprop="name">Ackermannn</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">22</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">2</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">14</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ackermannn" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ackermannn" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
  </div>



        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner index posts-expand">

    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/09/01/%E5%AD%97%E8%8A%82%E9%9D%A2%E8%AF%95%E9%A2%98%E2%80%94%E2%80%94%E8%BE%93%E5%87%BA%E5%8C%96%E5%AD%A6%E5%BC%8F%E4%B8%AD%E6%AF%8F%E4%B8%AA%E5%8E%9F%E5%AD%90%E7%9A%84%E4%B8%AA%E6%95%B0/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/09/01/%E5%AD%97%E8%8A%82%E9%9D%A2%E8%AF%95%E9%A2%98%E2%80%94%E2%80%94%E8%BE%93%E5%87%BA%E5%8C%96%E5%AD%A6%E5%BC%8F%E4%B8%AD%E6%AF%8F%E4%B8%AA%E5%8E%9F%E5%AD%90%E7%9A%84%E4%B8%AA%E6%95%B0/" class="post-title-link" itemprop="url">字节面试题——输出化学式中每个原子的个数</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2021-09-01 15:27:07 / 修改时间：15:29:42" itemprop="dateCreated datePublished" datetime="2021-09-01T15:27:07+08:00">2021-09-01</time>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/09/01/%E5%AD%97%E8%8A%82%E9%9D%A2%E8%AF%95%E9%A2%98%E2%80%94%E2%80%94%E8%BE%93%E5%87%BA%E5%8C%96%E5%AD%A6%E5%BC%8F%E4%B8%AD%E6%AF%8F%E4%B8%AA%E5%8E%9F%E5%AD%90%E7%9A%84%E4%B8%AA%E6%95%B0/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/09/01/%E5%AD%97%E8%8A%82%E9%9D%A2%E8%AF%95%E9%A2%98%E2%80%94%E2%80%94%E8%BE%93%E5%87%BA%E5%8C%96%E5%AD%A6%E5%BC%8F%E4%B8%AD%E6%AF%8F%E4%B8%AA%E5%8E%9F%E5%AD%90%E7%9A%84%E4%B8%AA%E6%95%B0/" class="cy_cmt_count" data-xid="2021/09/01/字节面试题——输出化学式中每个原子的个数/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>2021.8.31 某同学的字节一面手撕算法题</p>
<p>给出类似于 <code>HM2(H2ON3A)3N2</code> 这样的类化学表达式</p>
<p>输出每个原子的个数</p>
<p>看起来有点意思</p>
<p>思路：</p>
<p>遇到左括号亚栈 有括号弹出栈</p>
<p>栈中存放固定大小为元素总数的数组，其记录每个元素的出现次数</p>
<p>同时主要到字母后面与右括号的数字，讲栈顶记录的出现次数与其相乘即可。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 写上 所有 化学元素和 原子序数的对应 。这里比较懒先写几个用得到的</span></span><br><span class="line">DIC = &#123;</span><br><span class="line">    <span class="string">&#x27;H&#x27;</span>: <span class="number">0</span>,</span><br><span class="line">    <span class="string">&#x27;He&#x27;</span>: <span class="number">1</span>,</span><br><span class="line">    <span class="string">&#x27;Li&#x27;</span>: <span class="number">2</span>,</span><br><span class="line">    <span class="string">&#x27;C&#x27;</span>: <span class="number">5</span>,</span><br><span class="line">    <span class="string">&#x27;O&#x27;</span>: <span class="number">7</span>,</span><br><span class="line">    <span class="string">&#x27;S&#x27;</span>: <span class="number">15</span>,</span><br><span class="line">    <span class="string">&#x27;Al&#x27;</span>: <span class="number">12</span>,</span><br><span class="line">    <span class="string">&#x27;Cu&#x27;</span>: <span class="number">29</span>,</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">RE_DIC = &#123;</span><br><span class="line">    <span class="number">0</span>: <span class="string">&#x27;H&#x27;</span>,</span><br><span class="line">    <span class="number">1</span>: <span class="string">&#x27;He&#x27;</span>,</span><br><span class="line">    <span class="number">2</span>: <span class="string">&#x27;Li&#x27;</span>,</span><br><span class="line">    <span class="number">5</span>: <span class="string">&#x27;C&#x27;</span>,</span><br><span class="line">    <span class="number">7</span>: <span class="string">&#x27;O&#x27;</span>,</span><br><span class="line">    <span class="number">15</span>: <span class="string">&#x27;S&#x27;</span>,</span><br><span class="line">    <span class="number">12</span>: <span class="string">&#x27;Al&#x27;</span>,</span><br><span class="line">    <span class="number">29</span>: <span class="string">&#x27;Cu&#x27;</span>,</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">solve</span>(<span class="params">s</span>):</span></span><br><span class="line">    stack = [[<span class="number">0</span>] * <span class="number">100</span>]  <span class="comment"># 化学元素先设定一百个吧。每个栈帧是个数组 数组按照元素顺序存放着元素的出现次数</span></span><br><span class="line">    n = <span class="built_in">len</span>(s)</span><br><span class="line">    <span class="keyword">for</span> idx, item <span class="keyword">in</span> <span class="built_in">enumerate</span>(s):</span><br><span class="line">        <span class="keyword">if</span> item.isupper(): <span class="comment"># 化学元素名字总是一个大写字母开头后面都是小写字母</span></span><br><span class="line"></span><br><span class="line">            <span class="comment"># 支持多字符的元素，识别出类似于 Al Cu 这样的元素</span></span><br><span class="line">            end = idx + <span class="number">1</span></span><br><span class="line">            <span class="keyword">while</span> end &lt;= n - <span class="number">1</span> <span class="keyword">and</span> s[end].islower():</span><br><span class="line">                end += <span class="number">1</span></span><br><span class="line">            name = s[idx:end]</span><br><span class="line"></span><br><span class="line">            <span class="comment"># 记录右下缀 ,如 读出 Al2 中数字 2</span></span><br><span class="line">            times = <span class="number">1</span></span><br><span class="line">            <span class="keyword">if</span> end &lt;= n - <span class="number">1</span> <span class="keyword">and</span> s[end].isdecimal():</span><br><span class="line">                times = <span class="built_in">int</span>(s[end])</span><br><span class="line">            stack[-<span class="number">1</span>][DIC[name]] += times</span><br><span class="line"></span><br><span class="line">        <span class="keyword">elif</span> item == <span class="string">&#x27;(&#x27;</span>: <span class="comment"># 压栈</span></span><br><span class="line">            stack.append([<span class="number">0</span>] * <span class="number">100</span>)</span><br><span class="line"></span><br><span class="line">        <span class="keyword">elif</span> item == <span class="string">&#x27;)&#x27;</span>: <span class="comment"># 出栈</span></span><br><span class="line">            times = <span class="number">1</span></span><br><span class="line">            <span class="keyword">if</span> idx != n - <span class="number">1</span> <span class="keyword">and</span> s[idx + <span class="number">1</span>].isdecimal():  <span class="comment"># 如果 ) 后面是数字 要加倍</span></span><br><span class="line">                times = <span class="built_in">int</span>(s[idx + <span class="number">1</span>])</span><br><span class="line">            popped = stack.pop()</span><br><span class="line">            <span class="comment"># 把弹出的信息，合并到栈顶中去</span></span><br><span class="line">            <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(popped)):</span><br><span class="line">                stack[-<span class="number">1</span>][i] += popped[i] * times</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> stack</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&#x27;__main__&#x27;</span>:</span><br><span class="line">    <span class="comment"># s = &quot;Al2(SO4)3&quot;</span></span><br><span class="line">    s = <span class="string">&quot;Cu2(OH)2CO3&quot;</span></span><br><span class="line">    ret = solve(s)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">100</span>):</span><br><span class="line">        <span class="keyword">if</span> ret[<span class="number">0</span>][i] != <span class="number">0</span>:</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f&quot;原子<span class="subst">&#123;RE_DIC[i]&#125;</span> : <span class="subst">&#123;ret[<span class="number">0</span>][i]&#125;</span>&quot;</span>)</span><br></pre></td></tr></table></figure>

<p>输出</p>
<figure class="highlight ada"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">原子H : 2</span><br><span class="line">原子C : 1</span><br><span class="line">原子O : 5</span><br><span class="line">原子Cu : 2</span><br></pre></td></tr></table></figure>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/09/01/hello-world/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/09/01/hello-world/" class="post-title-link" itemprop="url">Hello World</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-09-01 15:23:22" itemprop="dateCreated datePublished" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/09/01/hello-world/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/09/01/hello-world/" class="cy_cmt_count" data-xid="2021/09/01/hello-world/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>Welcome to <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a>! This is your very first post. Check <a target="_blank" rel="noopener" href="https://hexo.io/docs/">documentation</a> for more info. If you get any problems when using Hexo, you can find the answer in <a target="_blank" rel="noopener" href="https://hexo.io/docs/troubleshooting.html">troubleshooting</a> or you can ask me on <a target="_blank" rel="noopener" href="https://github.com/hexojs/hexo/issues">GitHub</a>.</p>
<h2 id="Quick-Start"><a href="#Quick-Start" class="headerlink" title="Quick Start"></a>Quick Start</h2><h3 id="Create-a-new-post"><a href="#Create-a-new-post" class="headerlink" title="Create a new post"></a>Create a new post</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo new <span class="string">&quot;My New Post&quot;</span></span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/writing.html">Writing</a></p>
<h3 id="Run-server"><a href="#Run-server" class="headerlink" title="Run server"></a>Run server</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo server</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/server.html">Server</a></p>
<h3 id="Generate-static-files"><a href="#Generate-static-files" class="headerlink" title="Generate static files"></a>Generate static files</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo generate</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/generating.html">Generating</a></p>
<h3 id="Deploy-to-remote-sites"><a href="#Deploy-to-remote-sites" class="headerlink" title="Deploy to remote sites"></a>Deploy to remote sites</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo deploy</span><br></pre></td></tr></table></figure>

<p>More info: <a target="_blank" rel="noopener" href="https://hexo.io/docs/one-command-deployment.html">Deployment</a></p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/08/15/%E7%BE%8E%E5%9B%A22021-8-15%E7%9A%84%E4%B8%80%E4%B8%AA%E7%AC%94%E8%AF%95%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/08/15/%E7%BE%8E%E5%9B%A22021-8-15%E7%9A%84%E4%B8%80%E4%B8%AA%E7%AC%94%E8%AF%95%E9%A2%98/" class="post-title-link" itemprop="url">美团2021.8.15的一个笔试题</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-08-15 15:09:04" itemprop="dateCreated datePublished" datetime="2021-08-15T15:09:04+08:00">2021-08-15</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/08/15/%E7%BE%8E%E5%9B%A22021-8-15%E7%9A%84%E4%B8%80%E4%B8%AA%E7%AC%94%E8%AF%95%E9%A2%98/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/08/15/%E7%BE%8E%E5%9B%A22021-8-15%E7%9A%84%E4%B8%80%E4%B8%AA%E7%AC%94%E8%AF%95%E9%A2%98/" class="cy_cmt_count" data-xid="2021/08/15/美团2021-8-15的一个笔试题/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>参加美团笔试的其中一个笔试题，题干是以角色扮演类游戏为背景，计算角色对标靶的总攻击和。<br>没有记录下详细的题干，只有自己的代码。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Warrior</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, a, d, c2, c3, c4</span>):</span></span><br><span class="line">        self.INITIAL_ATTACK = a  <span class="comment"># 初始攻击力</span></span><br><span class="line">        self.MAX_ATTACK_BUFF_TIME = c2  <span class="comment"># 进攻buff 持续时间</span></span><br><span class="line">        self.MAX_AIM_DEFENCE = d  <span class="comment"># 目标最大防御力</span></span><br><span class="line">        self.MAX_DEFENCE_BUFF_TIME = c3  <span class="comment"># 减防buff持续时间</span></span><br><span class="line">        self.PERMANENCY_ATTACK_INCREASE = c4  <span class="comment"># 永久提升额</span></span><br><span class="line"></span><br><span class="line">        self.baseAttack = self.INITIAL_ATTACK  <span class="comment"># 基础攻击力</span></span><br><span class="line">        self.aimDefence = self.MAX_AIM_DEFENCE  <span class="comment"># 目标防御力</span></span><br><span class="line">        self.defenceBuffTime = <span class="number">0</span>  <span class="comment"># 减防buff剩余时间</span></span><br><span class="line">        self.attackBuffTimes = []  <span class="comment"># 攻击buff剩余时间</span></span><br><span class="line"></span><br><span class="line">        self.totalAttack = <span class="number">0</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">do1</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="comment"># 进攻</span></span><br><span class="line">        attack = (<span class="built_in">len</span>(self.attackBuffTimes) + <span class="number">1</span>) * self.baseAttack  <span class="comment"># 计算攻击力加成</span></span><br><span class="line"></span><br><span class="line">        defence = self.MAX_AIM_DEFENCE</span><br><span class="line">        <span class="keyword">if</span> self.defenceBuffTime &gt; <span class="number">0</span>:</span><br><span class="line">            defence = <span class="number">0</span></span><br><span class="line"></span><br><span class="line">        self.totalAttack += <span class="built_in">max</span>(<span class="number">1</span>, attack - defence)</span><br><span class="line">        self.final()</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">do2</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="comment"># 增加buff</span></span><br><span class="line">        self.attackBuffTimes.append(self.MAX_ATTACK_BUFF_TIME)</span><br><span class="line">        self.final()</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">do3</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="comment"># 刷新减防</span></span><br><span class="line">        self.defenceBuffTime = self.MAX_DEFENCE_BUFF_TIME</span><br><span class="line">        self.final()</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">do4</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="comment"># 增加永久攻击</span></span><br><span class="line">        self.baseAttack += self.PERMANENCY_ATTACK_INCREASE</span><br><span class="line">        self.final()</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">final</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="comment"># buff结算</span></span><br><span class="line">        <span class="keyword">if</span> <span class="number">0</span> <span class="keyword">in</span> self.attackBuffTimes: self.attackBuffTimes.remove(<span class="number">0</span>)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(self.attackBuffTimes)):</span><br><span class="line">            self.attackBuffTimes[i] -= <span class="number">1</span></span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> self.defenceBuffTime != <span class="number">0</span>:</span><br><span class="line">            self.defenceBuffTime -= <span class="number">0</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&#x27;__main__&#x27;</span>:</span><br><span class="line">    a = <span class="number">3</span></span><br><span class="line">    d = <span class="number">3</span></span><br><span class="line">    c2 = <span class="number">6</span></span><br><span class="line">    c3 = <span class="number">6</span></span><br><span class="line">    c4 = <span class="number">2</span></span><br><span class="line">    opt = <span class="string">&quot;121341&quot;</span></span><br><span class="line">    warrior = Warrior(a, d, c2, c3, c4)</span><br><span class="line">    <span class="keyword">for</span> c <span class="keyword">in</span> opt:</span><br><span class="line">        <span class="keyword">if</span> c == <span class="string">&#x27;1&#x27;</span>:</span><br><span class="line">            warrior.do1()</span><br><span class="line">        <span class="keyword">elif</span> c == <span class="string">&#x27;2&#x27;</span>:</span><br><span class="line">            warrior.do2()</span><br><span class="line">        <span class="keyword">elif</span> c == <span class="string">&#x27;3&#x27;</span>:</span><br><span class="line">            warrior.do3()</span><br><span class="line">        <span class="keyword">elif</span> c == <span class="string">&#x27;4&#x27;</span>:</span><br><span class="line">            warrior.do4()</span><br><span class="line">    <span class="built_in">print</span>(warrior.totalAttack)</span><br><span class="line">    <span class="comment"># while True:</span></span><br><span class="line">    <span class="comment">#     try:</span></span><br><span class="line">    <span class="comment">#         n, a, d, c2, c3, c4 = [int(i) for i in input().split()]</span></span><br><span class="line">    <span class="comment">#         opt = input()</span></span><br><span class="line">    <span class="comment">#         ans = solve(a, d, c2, c3, c4, opt)</span></span><br><span class="line">    <span class="comment">#         print(ans)</span></span><br><span class="line">    <span class="comment">#     except:</span></span><br><span class="line">    <span class="comment">#         break</span></span><br><span class="line"></span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/05/12/%E5%8A%9B%E6%89%A31310%E5%AD%90%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%9F%A5%E8%AF%A2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/05/12/%E5%8A%9B%E6%89%A31310%E5%AD%90%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%9F%A5%E8%AF%A2/" class="post-title-link" itemprop="url">力扣1310子数组异或查询</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-05-12 10:31:05" itemprop="dateCreated datePublished" datetime="2021-05-12T10:31:05+08:00">2021-05-12</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/05/12/%E5%8A%9B%E6%89%A31310%E5%AD%90%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%9F%A5%E8%AF%A2/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/05/12/%E5%8A%9B%E6%89%A31310%E5%AD%90%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%9F%A5%E8%AF%A2/" class="cy_cmt_count" data-xid="2021/05/12/力扣1310子数组异或查询/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="力扣1310子数组异或查询"><a href="#力扣1310子数组异或查询" class="headerlink" title="力扣1310子数组异或查询"></a>力扣1310子数组异或查询</h1><h2 id="问题"><a href="#问题" class="headerlink" title="问题"></a>问题</h2><p>有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。</p>
<p>对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。</p>
<p>并返回一个包含给定查询 queries 所有结果的数组。</p>
<p><strong>示例 1：</strong></p>
<blockquote>
<p>输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]<br>输出：[2,7,14,8]<br>解释：<br>数组中元素的二进制表示形式是：<br>1 = 0001<br>3 = 0011<br>4 = 0100<br>8 = 1000<br>查询的 XOR 值为：<br>[0,1] = 1 xor 3 = 2<br>[1,2] = 3 xor 4 = 7<br>[0,3] = 1 xor 3 xor 4 xor 8 = 14<br>[3,3] = 8</p>
</blockquote>
<p><strong>示例 2：</strong></p>
<blockquote>
<p>输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]<br>输出：[8,0,4,4]</p>
</blockquote>
<p><strong>提示：</strong></p>
<blockquote>
<p>1 &lt;= arr.length &lt;= 3 * 10^4<br>1 &lt;= arr[i] &lt;= 10^9<br>1 &lt;= queries.length &lt;= 3 * 10^4<br>queries[i].length == 2<br>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt; arr.length</p>
</blockquote>
<p>来源：力扣（LeetCode）</p>
<p>链接：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/xor-queries-of-a-subarray">https://leetcode-cn.com/problems/xor-queries-of-a-subarray</a></p>
<h2 id="解答"><a href="#解答" class="headerlink" title="解答"></a>解答</h2><p>前缀和的思想。使用暴力法会超时</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">xorQueries</span>(<span class="params">self, arr: <span class="type">List</span>[<span class="built_in">int</span>], queries: <span class="type">List</span>[<span class="type">List</span>[<span class="built_in">int</span>]]</span>) -&gt; <span class="type">List</span>[<span class="built_in">int</span>]:</span></span><br><span class="line">        <span class="string">&quot;&quot;&quot;XOR前缀和&quot;&quot;&quot;</span></span><br><span class="line">        pre = [<span class="number">0</span>]  <span class="comment"># 前缀数组</span></span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(arr)):</span><br><span class="line">            pre.append(arr[i] ^ pre[-<span class="number">1</span>])</span><br><span class="line">        res = []</span><br><span class="line">        <span class="keyword">for</span> a, b <span class="keyword">in</span> queries:</span><br><span class="line">            res.append(pre[a] ^ pre[b + <span class="number">1</span>])</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> res</span><br></pre></td></tr></table></figure>



<p>评论区<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/xor-queries-of-a-subarray/comments/214199">神解答</a></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">xorQueries</span>(<span class="params">self, arr: <span class="type">List</span>[<span class="built_in">int</span>], queries: <span class="type">List</span>[<span class="type">List</span>[<span class="built_in">int</span>]]</span>) -&gt; <span class="type">List</span>[<span class="built_in">int</span>]:</span></span><br><span class="line">        acc = <span class="built_in">list</span>(accumulate([<span class="number">0</span>] + arr, xor))</span><br><span class="line">        <span class="keyword">return</span> [acc[a] ^ acc[b + <span class="number">1</span>] <span class="keyword">for</span> a, b <span class="keyword">in</span> queries]</span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/05/08/%E5%8A%9B%E6%89%A3199%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%8F%B3%E8%A7%86%E5%9B%BE/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/05/08/%E5%8A%9B%E6%89%A3199%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%8F%B3%E8%A7%86%E5%9B%BE/" class="post-title-link" itemprop="url">力扣199二叉树的右视图</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-05-08 16:49:57" itemprop="dateCreated datePublished" datetime="2021-05-08T16:49:57+08:00">2021-05-08</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%8A%9B%E6%89%A3/" itemprop="url" rel="index"><span itemprop="name">力扣</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/05/08/%E5%8A%9B%E6%89%A3199%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%8F%B3%E8%A7%86%E5%9B%BE/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/05/08/%E5%8A%9B%E6%89%A3199%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%8F%B3%E8%A7%86%E5%9B%BE/" class="cy_cmt_count" data-xid="2021/05/08/力扣199二叉树的右视图/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="199-二叉树的右视图"><a href="#199-二叉树的右视图" class="headerlink" title="199. 二叉树的右视图"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/binary-tree-right-side-view/">199. 二叉树的右视图</a></h1><h2 id="问题"><a href="#问题" class="headerlink" title="问题"></a>问题</h2><p>给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。</p>
<p>示例:</p>
<figure class="highlight elm"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">输入: [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,null,<span class="number">5</span>,null,<span class="number">4</span>]</span><br><span class="line">输出: [<span class="number">1</span>, <span class="number">3</span>, <span class="number">4</span>]</span><br><span class="line">解释:</span><br><span class="line"></span><br><span class="line">   <span class="number">1</span>            &lt;-<span class="comment">--</span></span><br><span class="line"> /   \</span><br><span class="line"><span class="number">2</span>     <span class="number">3</span>         &lt;-<span class="comment">--</span></span><br><span class="line"> \     \</span><br><span class="line">  <span class="number">5</span>     <span class="number">4</span>       &lt;-<span class="comment">--</span></span><br></pre></td></tr></table></figure>
<p>来源：力扣（LeetCode）</p>
<p>链接：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/binary-tree-right-side-view">https://leetcode-cn.com/problems/binary-tree-right-side-view</a></p>
<h2 id="解答"><a href="#解答" class="headerlink" title="解答"></a>解答</h2><p>参考<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/binary-tree-right-side-view/comments/360687">甜姐的解答</a></p>
<blockquote>
<p>二、DFS<br>我们按照 「根结点 -&gt; 右子树 -&gt; 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。<br>（与先序遍历 「根结点 -&gt; 左子树 -&gt; 右子树」 正好相反，先序遍历每层最先访问的是最左边的节点）</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    List&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">rightSideView</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        dfs(root, <span class="number">0</span>);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(TreeNode root, <span class="keyword">int</span> depth)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span>;</span><br><span class="line">        <span class="keyword">if</span> (depth == res.size()) res.add(root.val);</span><br><span class="line">        dfs(root.right, depth + <span class="number">1</span>);</span><br><span class="line">        dfs(root.left, depth + <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/04/29/%E5%8A%9B%E6%89%A3403-%E9%9D%92%E8%9B%99%E8%BF%87%E6%B2%B3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/04/29/%E5%8A%9B%E6%89%A3403-%E9%9D%92%E8%9B%99%E8%BF%87%E6%B2%B3/" class="post-title-link" itemprop="url">力扣403.青蛙过河</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-04-29 19:22:36" itemprop="dateCreated datePublished" datetime="2021-04-29T19:22:36+08:00">2021-04-29</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%8A%9B%E6%89%A3/" itemprop="url" rel="index"><span itemprop="name">力扣</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/04/29/%E5%8A%9B%E6%89%A3403-%E9%9D%92%E8%9B%99%E8%BF%87%E6%B2%B3/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/04/29/%E5%8A%9B%E6%89%A3403-%E9%9D%92%E8%9B%99%E8%BF%87%E6%B2%B3/" class="cy_cmt_count" data-xid="2021/04/29/力扣403-青蛙过河/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h1><p><img src="https://pic.leetcode-cn.com/1619656977-DEvDOg-src=http___5b0988e595225.cdn.sohucs.com_images_20200508_327f15985a51404bb648f2f8e518045e.jpeg&refer=http___5b0988e595225.cdn.sohucs.jpeg" alt=""></p>
<p>一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。</p>
<p>给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。</p>
<p>开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。</p>
<p>如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。</p>
<p>示例 1：</p>
<blockquote>
<p>输入：stones = [0,1,3,5,6,8,12,17]<br>输出：true<br>解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。</p>
</blockquote>
<p>示例 2：</p>
<blockquote>
<p>输入：stones = [0,1,2,3,4,8,9,11]<br>输出：false<br>解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。</p>
</blockquote>
<p>提示：</p>
<blockquote>
<p>2 &lt;= stones.length &lt;= 2000<br>0 &lt;= stones[i] &lt;= 231 - 1<br>stones[0] == 0</p>
</blockquote>
<p>来源：力扣（LeetCode）</p>
<p>链接：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/frog-jump">https://leetcode-cn.com/problems/frog-jump</a></p>
<h1 id="解答"><a href="#解答" class="headerlink" title="解答"></a>解答</h1><p>用户 <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/frog-jump/solution/python-ji-yi-hua-hui-su-by-bryannliu-dgd0/">bryannliu</a> 的解答：</p>
<blockquote>
<p>这题和 55. 跳跃游戏 有点像，但是55 满足贪心选择性，所以直接用贪心算法做，这道题目因为有多种走法，所以得一个个试，用记忆化递归来做比较合适。</p>
<p>因为每次有三种走法，要尝试每种可能，肯定有重复计算，所以加上备忘录。</p>
<ol>
<li>状态定义和参数：s(i, step) 表示当前是第i块时候，通过step步过来的，</li>
<li>决策和状态转移：接下来就是根据走的步数做状态变换，这里状态变换只有三种 step-1, step, step + 1, 尝试每种可能的走法，看能不能走到最后一块。</li>
</ol>
</blockquote>
<p>我这里的 recur(start, k) 中的 start 表示 stones数组顺序下标</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">canCross</span>(<span class="params">self, stones: <span class="type">List</span>[<span class="built_in">int</span>]</span>) -&gt; <span class="built_in">bool</span>:</span></span><br><span class="line">        n = <span class="built_in">len</span>(stones)</span><br><span class="line"></span><br><span class="line"><span class="meta">        @lru_cache(<span class="params"><span class="literal">None</span></span>)</span></span><br><span class="line">        <span class="function"><span class="keyword">def</span> <span class="title">recur</span>(<span class="params">start, k</span>):</span></span><br><span class="line">            <span class="keyword">if</span> start &gt;= n - <span class="number">1</span>: <span class="keyword">return</span> <span class="literal">True</span></span><br><span class="line">            <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(start + <span class="number">1</span>, n):</span><br><span class="line">                <span class="keyword">if</span> stones[start] + k - <span class="number">1</span> == stones[i]:  <span class="comment"># 往后遍历找到 能以 k-1 步跳到的石子</span></span><br><span class="line">                    <span class="keyword">if</span> recur(i, k - <span class="number">1</span>): <span class="keyword">return</span> <span class="literal">True</span></span><br><span class="line">                <span class="keyword">if</span> stones[start] + k == stones[i]:  <span class="comment"># 往后遍历找到 能以 k 步跳到的石子</span></span><br><span class="line">                    <span class="keyword">if</span> recur(i, k): <span class="keyword">return</span> <span class="literal">True</span></span><br><span class="line">                <span class="keyword">if</span> stones[start] + k + <span class="number">1</span> == stones[i]:  <span class="comment"># 往后遍历找到 能以 k+1 步跳到的石子</span></span><br><span class="line">                    <span class="keyword">if</span> recur(i, k + <span class="number">1</span>): <span class="keyword">return</span> <span class="literal">True</span></span><br><span class="line">                <span class="keyword">if</span> stones[start] + k + <span class="number">1</span> &lt; stones[i]: <span class="keyword">break</span>  <span class="comment"># 因stones的单调性 提早结束遍历</span></span><br><span class="line">            <span class="keyword">return</span> <span class="literal">False</span></span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> recur(<span class="number">0</span>, <span class="number">0</span>)</span><br><span class="line"></span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/04/28/%E5%8A%9B%E6%89%A3300-%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/04/28/%E5%8A%9B%E6%89%A3300-%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97/" class="post-title-link" itemprop="url">力扣300.最长递增子序列</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-04-28 11:44:28" itemprop="dateCreated datePublished" datetime="2021-04-28T11:44:28+08:00">2021-04-28</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%8A%9B%E6%89%A3/" itemprop="url" rel="index"><span itemprop="name">力扣</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/04/28/%E5%8A%9B%E6%89%A3300-%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/04/28/%E5%8A%9B%E6%89%A3300-%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97/" class="cy_cmt_count" data-xid="2021/04/28/力扣300-最长递增子序列/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="问题"><a href="#问题" class="headerlink" title="问题"></a>问题</h1><p>给你一个整数数组 <code>nums</code> ，找到其中最长严格递增子序列的长度。</p>
<p>子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，<code>[3,6,2,7]</code> 是数组 <code>[0,3,1,6,2,2,7]</code> 的子序列。</p>
<p>示例 1：</p>
<blockquote>
<p>输入：nums = [10,9,2,5,3,7,101,18]<br>输出：4<br>解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。</p>
</blockquote>
<p>示例 2：</p>
<blockquote>
<p>输入：nums = [0,1,0,3,2,3]<br>输出：4</p>
</blockquote>
<p>示例 3：</p>
<blockquote>
<p>输入：nums = [7,7,7,7,7,7,7]<br>输出：1</p>
</blockquote>
<p>提示：</p>
<blockquote>
<p>1 &lt;= nums.length &lt;= 2500<br>-104 &lt;= nums[i] &lt;= 104</p>
</blockquote>
<p>进阶：</p>
<blockquote>
<p>你可以设计时间复杂度为 O(n2) 的解决方案吗？<br>你能将算法的时间复杂度降低到 O(n log(n)) 吗?</p>
</blockquote>
<p>来源：力扣（LeetCode）</p>
<p>链接：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-increasing-subsequence">https://leetcode-cn.com/problems/longest-increasing-subsequence</a></p>
<h1 id="解答"><a href="#解答" class="headerlink" title="解答"></a>解答</h1><p>引用 <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-increasing-subsequence/comments/284831">甜姨的评论</a></p>
<blockquote>
<p>相当于维护一个结果数组，如果当前元素比结果数组的值都大的的话，就追加在结果数组后面（相当于递增序列长度加了1）；否则的话用当前元素覆盖掉第一个比它大的元素（这样做的话后续递增序列才有可能更长，即使并没有更长，这个覆盖操作也并没有副作用哈，当然这个覆盖操作可能会让最终的结果数组值并不是最终的递增序列值，这无所谓）</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lengthOfLIS</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span>[] res = <span class="keyword">new</span> <span class="keyword">int</span>[nums.length];</span><br><span class="line">        <span class="keyword">int</span> len = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> num: nums) &#123;</span><br><span class="line">            <span class="keyword">int</span> idx = Arrays.binarySearch(res, <span class="number">0</span>, len, num);</span><br><span class="line">            idx = idx &lt; <span class="number">0</span>? -idx - <span class="number">1</span>: idx;</span><br><span class="line">            res[idx] = num;</span><br><span class="line">            <span class="keyword">if</span> (idx == len) &#123;</span><br><span class="line">                len++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> len;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这里给出我的使用二分法API的Python版</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">lengthOfLIS</span>(<span class="params">self, nums: <span class="type">List</span>[<span class="built_in">int</span>]</span>) -&gt; <span class="built_in">int</span>:</span></span><br><span class="line">        res = []</span><br><span class="line">        <span class="keyword">for</span> x <span class="keyword">in</span> nums:</span><br><span class="line">            loc = bisect.bisect_left(res, x)</span><br><span class="line">            <span class="keyword">if</span> loc == <span class="built_in">len</span>(res):</span><br><span class="line">                res.append(x)</span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                res[loc] = x</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">len</span>(res)</span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/04/27/%E5%BB%BA%E7%AB%8B%E6%89%93%E5%8D%B0%E5%8A%9B%E6%89%A3-Leetcode-%E4%B8%AD%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91-java/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/04/27/%E5%BB%BA%E7%AB%8B%E6%89%93%E5%8D%B0%E5%8A%9B%E6%89%A3-Leetcode-%E4%B8%AD%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91-java/" class="post-title-link" itemprop="url">建立打印力扣(Leetcode)中的二叉树-java</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-04-27 09:53:27" itemprop="dateCreated datePublished" datetime="2021-04-27T09:53:27+08:00">2021-04-27</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%8A%9B%E6%89%A3/" itemprop="url" rel="index"><span itemprop="name">力扣</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/04/27/%E5%BB%BA%E7%AB%8B%E6%89%93%E5%8D%B0%E5%8A%9B%E6%89%A3-Leetcode-%E4%B8%AD%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91-java/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/04/27/%E5%BB%BA%E7%AB%8B%E6%89%93%E5%8D%B0%E5%8A%9B%E6%89%A3-Leetcode-%E4%B8%AD%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91-java/" class="cy_cmt_count" data-xid="2021/04/27/建立打印力扣-Leetcode-中的二叉树-java/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="建立打印LeetCode中的二叉树"><a href="#建立打印LeetCode中的二叉树" class="headerlink" title="建立打印LeetCode中的二叉树"></a>建立打印LeetCode中的二叉树</h1><p>在刷力扣题时遇到二叉树的问题时，建树较为麻烦，打印树更加是不方便。</p>
<p>因为力扣中二叉树定义多为</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">TreeNode</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> val;</span><br><span class="line">    TreeNode left;</span><br><span class="line">    TreeNode right;</span><br><span class="line">    TreeNode(<span class="keyword">int</span> val) &#123; <span class="keyword">this</span>.val = val; &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>再增加建树的成员方法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> TreeNode <span class="title">creatABitTree</span><span class="params">(Integer[] nums)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (nums.length == <span class="number">0</span> || nums[<span class="number">0</span>] == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">if</span> (nums.length == <span class="number">1</span>) <span class="keyword">return</span> <span class="keyword">new</span> TreeNode(nums[<span class="number">0</span>]);</span><br><span class="line"></span><br><span class="line">    Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();  <span class="comment">// 得用队列</span></span><br><span class="line">    <span class="comment">// 根结点的处理</span></span><br><span class="line">    TreeNode node = <span class="keyword">new</span> TreeNode(nums[<span class="number">0</span>]);</span><br><span class="line">    queue.offer(node);</span><br><span class="line"></span><br><span class="line">    TreeNode temp;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; nums.length; ) &#123;</span><br><span class="line">        temp = queue.poll();</span><br><span class="line">        <span class="keyword">if</span> (nums[i] != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">assert</span> temp != <span class="keyword">null</span>;</span><br><span class="line">            temp.left = <span class="keyword">new</span> TreeNode(nums[i++]);</span><br><span class="line">            queue.offer(temp.left);</span><br><span class="line">        &#125; <span class="keyword">else</span></span><br><span class="line">            i++;</span><br><span class="line">        <span class="keyword">if</span> (i &gt;= nums.length)</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">if</span> (nums[i] != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">assert</span> temp != <span class="keyword">null</span>;</span><br><span class="line">            temp.right = <span class="keyword">new</span> TreeNode(nums[i++]);</span><br><span class="line">            queue.offer(temp.right);</span><br><span class="line">        &#125; <span class="keyword">else</span></span><br><span class="line">            i++;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


<p>参考 StackOverflow中<a target="_blank" rel="noopener" href="https://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram/8948691#8948691">How to print binary tree diagram?</a>这个问答，再添加树的打印方法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> StringBuilder <span class="title">toString</span><span class="params">(StringBuilder prefix, <span class="keyword">boolean</span> isTail, StringBuilder sb)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (right != <span class="keyword">null</span>) &#123;</span><br><span class="line">        right.toString(<span class="keyword">new</span> StringBuilder().append(prefix).append(isTail ? <span class="string">&quot;│   &quot;</span> : <span class="string">&quot;    &quot;</span>), <span class="keyword">false</span>, sb);</span><br><span class="line">    &#125;</span><br><span class="line">    sb.append(prefix).append(isTail ? <span class="string">&quot;└── &quot;</span> : <span class="string">&quot;┌── &quot;</span>).append(val).append(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">    <span class="keyword">if</span> (left != <span class="keyword">null</span>) &#123;</span><br><span class="line">        left.toString(<span class="keyword">new</span> StringBuilder().append(prefix).append(isTail ? <span class="string">&quot;    &quot;</span> : <span class="string">&quot;│   &quot;</span>), <span class="keyword">true</span>, sb);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> sb;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="meta">@Override</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">this</span>.toString(<span class="keyword">new</span> StringBuilder(), <span class="keyword">true</span>, <span class="keyword">new</span> StringBuilder()).toString();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="测试"><a href="#测试" class="headerlink" title="测试"></a>测试</h1><p>使用以下测试函数</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Main</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        TreeNode treeNode = TreeNode.creatABitTree(<span class="keyword">new</span> Integer[]&#123;</span><br><span class="line">                <span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span></span><br><span class="line">        &#125;);</span><br><span class="line">        System.out.println(treeNode);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>获得的测试结果：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">│       ┌── 6</span><br><span class="line">│   ┌── 2</span><br><span class="line">│   │   └── 5</span><br><span class="line">└── 0</span><br><span class="line">    │   ┌── 4</span><br><span class="line">    └── 1</span><br><span class="line">        └── 3</span><br></pre></td></tr></table></figure>


<h1 id="完整的TreeNode类"><a href="#完整的TreeNode类" class="headerlink" title="完整的TreeNode类"></a>完整的TreeNode类</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.LinkedList;</span><br><span class="line"><span class="keyword">import</span> java.util.Queue;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * create time: 2021/3/9 上午 10:01</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> DownUpZ</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">TreeNode</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> val;</span><br><span class="line">    TreeNode left;</span><br><span class="line">    TreeNode right;</span><br><span class="line"></span><br><span class="line">    TreeNode(<span class="keyword">int</span> val) &#123;</span><br><span class="line">        <span class="keyword">this</span>.val = val;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/***</span></span><br><span class="line"><span class="comment">     * 不选择 int[] 原因是 int 无法表示空</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> nums</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> TreeNode <span class="title">creatABitTree</span><span class="params">(Integer[] nums)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (nums.length == <span class="number">0</span> || nums[<span class="number">0</span>] == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">if</span> (nums.length == <span class="number">1</span>) <span class="keyword">return</span> <span class="keyword">new</span> TreeNode(nums[<span class="number">0</span>]);</span><br><span class="line"></span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();  <span class="comment">// 得用队列</span></span><br><span class="line">        <span class="comment">// 根结点的处理</span></span><br><span class="line">        TreeNode node = <span class="keyword">new</span> TreeNode(nums[<span class="number">0</span>]);</span><br><span class="line">        queue.offer(node);</span><br><span class="line"></span><br><span class="line">        TreeNode temp;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; nums.length; ) &#123;</span><br><span class="line">            temp = queue.poll();</span><br><span class="line">            <span class="keyword">if</span> (nums[i] != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">assert</span> temp != <span class="keyword">null</span>;</span><br><span class="line">                temp.left = <span class="keyword">new</span> TreeNode(nums[i++]);</span><br><span class="line">                queue.offer(temp.left);</span><br><span class="line">            &#125; <span class="keyword">else</span></span><br><span class="line">                i++;</span><br><span class="line">            <span class="keyword">if</span> (i &gt;= nums.length)</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">if</span> (nums[i] != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">assert</span> temp != <span class="keyword">null</span>;</span><br><span class="line">                temp.right = <span class="keyword">new</span> TreeNode(nums[i++]);</span><br><span class="line">                queue.offer(temp.right);</span><br><span class="line">            &#125; <span class="keyword">else</span></span><br><span class="line">                i++;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> StringBuilder <span class="title">toString</span><span class="params">(StringBuilder prefix, <span class="keyword">boolean</span> isTail, StringBuilder sb)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (right != <span class="keyword">null</span>) &#123;</span><br><span class="line">            right.toString(<span class="keyword">new</span> StringBuilder().append(prefix).append(isTail ? <span class="string">&quot;│   &quot;</span> : <span class="string">&quot;    &quot;</span>), <span class="keyword">false</span>, sb);</span><br><span class="line">        &#125;</span><br><span class="line">        sb.append(prefix).append(isTail ? <span class="string">&quot;└── &quot;</span> : <span class="string">&quot;┌── &quot;</span>).append(val).append(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">        <span class="keyword">if</span> (left != <span class="keyword">null</span>) &#123;</span><br><span class="line">            left.toString(<span class="keyword">new</span> StringBuilder().append(prefix).append(isTail ? <span class="string">&quot;    &quot;</span> : <span class="string">&quot;│   &quot;</span>), <span class="keyword">true</span>, sb);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sb;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">this</span>.toString(<span class="keyword">new</span> StringBuilder(), <span class="keyword">true</span>, <span class="keyword">new</span> StringBuilder()).toString();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/04/27/%E5%8A%9B%E6%89%A3938-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E8%8C%83%E5%9B%B4%E5%92%8C/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/04/27/%E5%8A%9B%E6%89%A3938-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E8%8C%83%E5%9B%B4%E5%92%8C/" class="post-title-link" itemprop="url">力扣938.二叉搜索树的范围和</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-04-27 09:37:28" itemprop="dateCreated datePublished" datetime="2021-04-27T09:37:28+08:00">2021-04-27</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%8A%9B%E6%89%A3/" itemprop="url" rel="index"><span itemprop="name">力扣</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/04/27/%E5%8A%9B%E6%89%A3938-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E8%8C%83%E5%9B%B4%E5%92%8C/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/04/27/%E5%8A%9B%E6%89%A3938-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E8%8C%83%E5%9B%B4%E5%92%8C/" class="cy_cmt_count" data-xid="2021/04/27/力扣938-二叉搜索树的范围和/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h1><p>给定二叉搜索树的根结点 root，返回值位于范围 <code>[low, high]</code> 之间的所有结点的值的和。</p>
<p>示例 1：</p>
<p><img src="images/leetcode/938bst1.jpg" alt="二叉搜索树1"></p>
<figure class="highlight nix"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：<span class="attr">root</span> = [<span class="number">10</span>,<span class="number">5</span>,<span class="number">15</span>,<span class="number">3</span>,<span class="number">7</span>,<span class="literal">null</span>,<span class="number">18</span>], <span class="attr">low</span> = <span class="number">7</span>, <span class="attr">high</span> = <span class="number">15</span></span><br><span class="line">输出：<span class="number">32</span></span><br></pre></td></tr></table></figure>
<p>示例 2：</p>
<p><img src="images/leetcode/938bst2.jpg" alt="二叉搜索树2"></p>
<figure class="highlight nix"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">输入：<span class="attr">root</span> = [<span class="number">10</span>,<span class="number">5</span>,<span class="number">15</span>,<span class="number">3</span>,<span class="number">7</span>,<span class="number">13</span>,<span class="number">18</span>,<span class="number">1</span>,<span class="literal">null</span>,<span class="number">6</span>], <span class="attr">low</span> = <span class="number">6</span>, <span class="attr">high</span> = <span class="number">10</span></span><br><span class="line">输出：<span class="number">23</span></span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p>提示：</p>
<figure class="highlight reasonml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">树中节点数目在范围 <span class="literal">[<span class="number">1</span>, <span class="number">2</span> <span class="operator">*</span> <span class="number">104</span>]</span> 内</span><br><span class="line"><span class="number">1</span> &lt;= <span class="module-access"><span class="module"><span class="identifier">Node</span>.</span></span><span class="keyword">val</span> &lt;= <span class="number">105</span></span><br><span class="line"><span class="number">1</span> &lt;= low &lt;= high &lt;= <span class="number">105</span></span><br><span class="line">所有 <span class="module-access"><span class="module"><span class="identifier">Node</span>.</span></span><span class="keyword">val</span> 互不相同</span><br></pre></td></tr></table></figure>

<p>来源：力扣（LeetCode）</p>
<p>链接：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/range-sum-of-bst">https://leetcode-cn.com/problems/range-sum-of-bst</a></p>
<h1 id="解答"><a href="#解答" class="headerlink" title="解答"></a>解答</h1><p>一道简单题，中序遍历递归即可</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">rangeSumBST</span><span class="params">(TreeNode root, <span class="keyword">int</span> low, <span class="keyword">int</span> high)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> leftVal = rangeSumBST(root.left, low, high);</span><br><span class="line">        <span class="keyword">int</span> midVal = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (low &lt;= root.val &amp;&amp; root.val &lt;= high) midVal = root.val;</span><br><span class="line">        <span class="keyword">int</span> rightVal = rangeSumBST(root.right, low, high);</span><br><span class="line">        <span class="keyword">return</span> leftVal + midVal + rightVal;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://ackermannn.github.io/2021/04/26/1011-%E5%9C%A8D%E5%A4%A9%E5%86%85%E9%80%81%E8%BE%BE%E5%8C%85%E8%A3%B9%E7%9A%84%E8%83%BD%E5%8A%9B/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/dl.jpg">
      <meta itemprop="name" content="Ackermannn">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Ackermannn's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2021/04/26/1011-%E5%9C%A8D%E5%A4%A9%E5%86%85%E9%80%81%E8%BE%BE%E5%8C%85%E8%A3%B9%E7%9A%84%E8%83%BD%E5%8A%9B/" class="post-title-link" itemprop="url">力扣1011.在D天内送达包裹的能力</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2021-04-26 09:18:59" itemprop="dateCreated datePublished" datetime="2021-04-26T09:18:59+08:00">2021-04-26</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-09-01 15:23:22" itemprop="dateModified" datetime="2021-09-01T15:23:22+08:00">2021-09-01</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%8A%9B%E6%89%A3/" itemprop="url" rel="index"><span itemprop="name">力扣</span></a>
        </span>
    </span>

  
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Changyan：</span>
    
    
      <a title="changyan" href="/2021/04/26/1011-%E5%9C%A8D%E5%A4%A9%E5%86%85%E9%80%81%E8%BE%BE%E5%8C%85%E8%A3%B9%E7%9A%84%E8%83%BD%E5%8A%9B/#SOHUCS" itemprop="discussionUrl">
        <span id="url::http://ackermannn.github.io/2021/04/26/1011-%E5%9C%A8D%E5%A4%A9%E5%86%85%E9%80%81%E8%BE%BE%E5%8C%85%E8%A3%B9%E7%9A%84%E8%83%BD%E5%8A%9B/" class="cy_cmt_count" data-xid="2021/04/26/1011-在D天内送达包裹的能力/" itemprop="commentCount"></span>
      </a>
    
  </span>
  
  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="问题"><a href="#问题" class="headerlink" title="问题"></a>问题</h1><p>传送带上的包裹必须在 <code>D</code> 天内从一个港口运送到另一个港口。</p>
<p>传送带上的第 <code>i</code> 个包裹的重量为 <code>weights[i]</code>。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。</p>
<p>返回能在 <code>D</code> 天内将传送带上的所有包裹送达的船的最低运载能力。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight tap"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5</span><br><span class="line">输出：15</span><br><span class="line">解释：</span><br><span class="line">船舶最低载重<span class="number"> 15 </span>就能够在<span class="number"> 5 </span>天内送达所有包裹，如下所示：</span><br><span class="line">第<span class="number"> 1 </span>天：1, 2, 3, 4, 5</span><br><span class="line">第<span class="number"> 2 </span>天：6, 7</span><br><span class="line">第<span class="number"> 3 </span>天：8</span><br><span class="line">第<span class="number"> 4 </span>天：9</span><br><span class="line">第<span class="number"> 5 </span>天：10</span><br><span class="line"></span><br><span class="line">请注意，货物必须按照给定的顺序装运，因此使用载重能力为<span class="number"> 14 </span>的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 </span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight tap"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">输入：weights = [3,2,2,4,1,4], D = 3</span><br><span class="line">输出：6</span><br><span class="line">解释：</span><br><span class="line">船舶最低载重<span class="number"> 6 </span>就能够在<span class="number"> 3 </span>天内送达所有包裹，如下所示：</span><br><span class="line">第<span class="number"> 1 </span>天：3, 2</span><br><span class="line">第<span class="number"> 2 </span>天：2, 4</span><br><span class="line">第<span class="number"> 3 </span>天：1, 4</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight tap"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">输入：weights = [1,2,3,1,1], D = 4</span><br><span class="line">输出：3</span><br><span class="line">解释：</span><br><span class="line">第<span class="number"> 1 </span>天：1</span><br><span class="line">第<span class="number"> 2 </span>天：2</span><br><span class="line">第<span class="number"> 3 </span>天：3</span><br><span class="line">第<span class="number"> 4 </span>天：1, 1</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<figure class="highlight basic"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="symbol">1 </span>&lt;= D &lt;= weights.length &lt;= <span class="number">50000</span></span><br><span class="line"><span class="symbol">1 </span>&lt;= weights[i] &lt;= <span class="number">500</span></span><br></pre></td></tr></table></figure>

<p>来源：<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days">链接</a></p>
<h1 id="解答"><a href="#解答" class="headerlink" title="解答"></a>解答</h1><p>二分法</p>
<p>引用用户<a target="_blank" rel="noopener" href="https://leetcode-cn.com/u/jiayangwu/">@Celia</a>的<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/comments/46984">解释</a>：</p>
<blockquote>
<p>二分查找，根据题意，结果一定落在【max(weights), sum(weights）】这个区间之间，因为左端点对应每天一条船，右端点对应只有一条超级大船。 然后利用二分法，每一次循环模拟运货的过程，然后根据需要的天数与 输入 D 的关系来调整区间左右端点。</p>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">shipWithinDays</span>(<span class="params">self, weights: <span class="type">List</span>[<span class="built_in">int</span>], D: <span class="built_in">int</span></span>) -&gt; <span class="built_in">int</span>:</span></span><br><span class="line">        l, r = <span class="built_in">max</span>(weights), <span class="built_in">sum</span>(weights)</span><br><span class="line">        <span class="keyword">while</span> l &lt; r:</span><br><span class="line">            mid = (l + r) // <span class="number">2</span></span><br><span class="line">            <span class="keyword">if</span> self.isEnough(weights, D, mid) <span class="keyword">is</span> <span class="literal">False</span>:</span><br><span class="line">                l = mid + <span class="number">1</span></span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                r = mid</span><br><span class="line">        <span class="keyword">return</span> l</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">isEnough</span>(<span class="params">self, weights, D, load</span>):</span></span><br><span class="line">        curD, curLoad = <span class="number">1</span>, <span class="number">0</span></span><br><span class="line">        <span class="keyword">for</span> w <span class="keyword">in</span> weights:</span><br><span class="line">            <span class="keyword">if</span> curLoad + w &gt; load:</span><br><span class="line">                curLoad = w</span><br><span class="line">                curD += <span class="number">1</span></span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                curLoad += w</span><br><span class="line">            <span class="keyword">if</span> curD &gt; D: <span class="keyword">return</span> <span class="literal">False</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">True</span></span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




  <nav class="pagination">
    <span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="page-number" href="/page/3/">3</a><a class="extend next" rel="next" href="/page/2/"><i class="fa fa-angle-right" aria-label="下一页"></i></a>
  </nav>


<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Ackermannn</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script size="300" alpha="0.6" zIndex="-1" src="https://cdn.jsdelivr.net/npm/ribbon.js@1.0.2/dist/ribbon.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/@next-theme/pjax@0.4.0/pjax.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script><script>
var pjax = new Pjax({
  selectors: [
    'head title',
    '.page-configurations',
    '.main-inner',
    '.post-toc-wrap',
    '.languages',
    '.pjax'
  ],
  analytics: false,
  cacheBust: false,
  scrollRestoration: false,
  scrollTo: !CONFIG.bookmark.enable
});

document.addEventListener('pjax:success', () => {
  pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
  NexT.boot.refresh();
  // Define Motion Sequence & Bootstrap Motion.
  if (CONFIG.motion.enable) {
    NexT.motion.integrator
      .init()
      .add(NexT.motion.middleWares.subMenu)
      .add(NexT.motion.middleWares.postList)
      .bootstrap();
  }
  const hasTOC = document.querySelector('.post-toc');
  document.querySelector('.sidebar-inner').classList.toggle('sidebar-nav-active', hasTOC);
  document.querySelector(hasTOC ? '.sidebar-nav-toc' : '.sidebar-nav-overview').click();
  NexT.utils.updateSidebarPosition();
});
</script>


  
<script src="/js/local-search.js"></script>





  <script>
    NProgress.configure({
      showSpinner: true
    });
    NProgress.start();
    document.addEventListener('readystatechange', () => {
      if (document.readyState === 'interactive') {
        NProgress.inc(0.8);
      }
      if (document.readyState === 'complete') {
        NProgress.done();
      }
    });
    document.addEventListener('pjax:send', () => {
      NProgress.start();
    });
    document.addEventListener('pjax:success', () => {
      NProgress.done();
    });
  </script>

  



    <div class="pjax">


  <script id="cy_cmt_num" src="https://changyan.sohu.com/upload/plugins/plugins.list.count.js?clientId=cyvq67Edd"></script>


    </div>
</body>
</html>
